package leetcode

import kotlinetc.println

//https://leetcode.com/problems/maximum-subarray/

/**
Share
Given an integer sort.getArray nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
 */
fun main(args: Array<String>) {

    maxSubArray(intArrayOf(-2, 1)).println()
}

//Classic 经典思路
fun maxSubArray(nums: IntArray): Int {

    var result = nums[0]
    var sum = 0
    nums.forEach { it ->
        //原理就是：如果之前和加上当前数字 比当前数字大，那么加入，反之从当前数开始
        sum = Math.max(sum + it, it)
        result = Math.max(result, sum)
    }
    return result

}

fun maxSubArrayDivideAndConquer(nums: IntArray): Int {


    return -1
}